from re import X
from pythonds.graphs import Vertex, Graph, dijkstra

graph = Graph()
path = [
    ["u", "v", 2],
    ["u", "x", 1],
    ["v", "x", 2],
    ["u", "w", 5],
    ["v", "w", 3],
    ["x", "w", 3],
    ["x", "y", 1],
    ["w", "y", 1],
    ["w", "z", 5],
    ["y", "z", 1],
]

for st, ed, val in path:
    graph.add_edge(st, ed, val)
    graph.add_edge(ed, st, val)

start = graph.get_vertex("u")
end = graph.get_vertex("z")

dijkstra(graph, start)

for vert in graph:
    ls = [vert.get_id()]
    pred = vert.get_pred()
    while pred:
        ls.append(pred.get_id())
        pred = pred.get_pred()

    ls.reverse()
    print(vert.get_distance(), "->".join(ls))
